package day_2022_4_to_7.nowcoder;

/**
 * 调整数组顺序使奇数位于偶数前面,相对位置不能改变
 * @author haomin
 * @date 2022/04/11 17:29
 **/
public class SortOddEvenNumber_10f {
    public static void main(String[] args) {
        int[] arr={1,2,3,4,5,6};
        reOrderArray1(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

    // 若相对位置可以改变，使用二分法
    public static void reOrderArray1(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right){
            // &运算 0&1=0，1&1=1，1&0=0，0&0=0
            while ((array[left] & 1) == 1 && left < right){
                // 找到偶数
                left++;
            }
            while ((array[right] & 1) == 0 && left < right){
                // 找到奇数
                right--;
            }
            if(left < right){
                // 交换三联
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
        }
    }

    // 因为相对位置不能改变，不能用二分法，用直接插入
    public static void reOrderArray2(int [] array) {
        // 记录已排奇数的末位置索引
        int k = 0;
        for (int i = 0; i < array.length; i++) {
            // &运算 0&1=0，1&1=1，1&0=0，0&0=0
            // 找到奇数
            if((array[i] & 1) == 1){
                int temp = array[i];
                int j = i;
                // 将 k~j 的偶数后移
                while(k < j){
                    array[j] = array[j-1];
                    j--;
                }
                array[k] = temp;
                k++;
            }
        }
    }
}